package sit.engreal.leetcode.problems100;

import sit.engreal.leetcode.util.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * <a herf="https://leetcode.cn/problems/binary-tree-inorder-traversal/">94. 二叉树的中序遍历</a>
 */
public class LeetCode94 {
    private static final TreeNode nil = new TreeNode();

    public List<Integer> inorderTraversal(TreeNode root) {
        final ArrayList<Integer> list = new ArrayList<>();
        final ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offerLast(root == null ? nil : root);
        for (; ; ) {
            while (deque.peekLast() != nil) {
                final TreeNode node = deque.peekLast();
                deque.offerLast(node.left == null ? nil : node.left);
            }
            deque.pollLast();
            if (deque.isEmpty()) {
                return list;
            }
            final TreeNode node = deque.pollLast();
            list.add(node.val);
            deque.offerLast(node.right == null ? nil : node.right);
        }
    }
}
